package offerbook.Code28_recallback_回溯_N皇后_排列;


/**
 * Created at 2019/10/25 0025 下午 10:16
 * <p>
 * 在全排列的基础上，当进行到当前位置交换 ，就检查对角线是否满足。
 * 因为行和列肯定满足
 */
public class Code28_Nqueen3 {


    public static int printNqueen(int n) {
        if (n <= 0) {
            return 0;
        }
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = i;
        }
        int[]res = {0};
        process(array, 0,res);
        return res[0];
    }

    private static void process(int[] array, int index,int[]res) {

        //所有的都通过了，加1并打印
        if (index == array.length) {
            res[0]++;
//            print(array);
            return;
        }
        //全排列
        for (int i = index; i < array.length; i++) {
            swap(array, i, index);
            //因为当前的行和列一定满足条件，判断当前对角线是否满足，是的话则继续，否则放弃
            if(check(array,index)){
                process(array, index + 1,res);
            }
            swap(array, index, i);
        }
    }
    //判断是否在同一对角线上，是的话，不满足条件
    private static boolean check(int[] array,int index) {

        //前0-index-2肯定不在对角线上了，所以只要判断index-1和 0-index-2是否在对角线上即可
        for (int i = 0; i < index; i++) {
            if (Math.abs(index - i) == Math.abs(array[index] - array[i])) {
                return false;
            }
        }
        return true;
    }



    private static void swap(int[] array, int i, int j) {
        if(i != j){
            array[i] = array[i] ^ array[j];
            array[j] = array[i] ^ array[j];
            array[i] = array[i] ^ array[j];
        }
    }

    //打印皇后摆法数量
    private static void print(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + 1 + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {

        long start = System.currentTimeMillis();
        int totalCount = printNqueen(14);
        //14个用时3.6s
        System.out.println("用时 = " + (System.currentTimeMillis() - start));
        System.out.println("totalCount = " + totalCount);

    }

}
